#ifndef __ARITHMETICS_H__
#define __ARITHMETICS_H__

////////////////////////////////////////////////////////////////////////////////
// Includes
////////////////////////////////////////////////////////////////////////////////

#include <string>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <map>
#include "Tokeniser.hpp"
#include "SimpleNode.hpp"
#include "ArithmeticsException.hpp"
#include "DivisionByZeroException.hpp"

////////////////////////////////////////////////////////////////////////////////
// Namespaces
////////////////////////////////////////////////////////////////////////////////

namespace Toolkit  {

////////////////////////////////////////////////////////////////////////////////
// Implementation
////////////////////////////////////////////////////////////////////////////////

// Light C style interface
#define ParseIntExp			Arithmetics::ParseExpression<int>
#define EvalIntExp			Arithmetics::EvalExpression<int>
#define ParseEvalIntExp		Arithmetics::ParseAndEvalExpression<int>

/**
 *  This class provides conversion function
 */
class Arithmetics {
	
	public:

		/**
		 *	Convert an arithmetic expression to a tree
		 */
		static Types::SimpleNode<std::string> ParseExpression(const std::string & expr) {
			using namespace Types;
			using namespace std;
			// Setup parser
			stringstream ss_expr;
			ss_expr << expr;
			Tokeniser parser(ss_expr);
			parser.AddSkipSymbol(" ");
			parser.AddSkipSymbol("\t");
			parser.AddSkipSymbol("\n");
			parser.AddSpecialSymbol("("); parser.AddSpecialSymbol(")");
			parser.AddSpecialSymbol("%");
			parser.AddSpecialSymbol("^");
			parser.AddSpecialSymbol("*"); parser.AddSpecialSymbol("/");
			parser.AddSpecialSymbol("+"); parser.AddSpecialSymbol("-");
			std::string left, right;
			// Remove useless brackets
			if (parser.PreviewNextToken(false) == "(") {
				parser.GetNextToken(false);
				int cpt = 0;
				while (!parser.PreviewNextToken(false).empty() && (cpt >= 0)) {
					if (parser.PreviewNextToken(false) == "(") ++cpt;
					else if (parser.PreviewNextToken(false) == ")") --cpt;
					if (cpt >= 0) left += parser.GetNextToken(false);
					else parser.GetNextToken(false);
				}
				// If useless brackets, remove them from the stream
				if ((cpt == -1) && parser.PreviewNextToken(false).empty()) {
					parser.Reset();
					ss_expr.str(left);
				}
			}
			// Check that expression is not empty
			if (parser.PreviewNextToken(false).empty())
				throw Exceptions::ArithmeticsException("Syntax error in arithmetic expression");
			// Look for +
			if (seek(parser,"+",left,right)) {
				SimpleNode<string> node("+");
				node.AddSubNode(ParseExpression(left));
				node.AddSubNode(ParseExpression(right));
				return node;
			}
			// Otherwise, look for -
			else if (seek(parser,"-",left,right)) {
				SimpleNode<string> node("-");
				node.AddSubNode(ParseExpression(left));
				node.AddSubNode(ParseExpression(right));
				return node;
			}
			// Otherwise,
			else {
				std::string left2, right2;
				bool 	op1 = seek(parser,"*",left,right),
						op2 = seek(parser,"/",left2,right2);
				// Look for * or /
				if (op1 || op2) {
					if (left.size() < left2.size()) {
						SimpleNode<string> node("*");
						node.AddSubNode(ParseExpression(left));
						node.AddSubNode(ParseExpression(right));
						return node;
					}
					else {
						SimpleNode<string> node("/");
						node.AddSubNode(ParseExpression(left2));
						node.AddSubNode(ParseExpression(right2));
						return node;
					}
				}
				// Otherwise, look for ^
				else if (seek(parser,"^",left,right)) {
					SimpleNode<string> node("^");
					node.AddSubNode(ParseExpression(left));
					node.AddSubNode(ParseExpression(right));
					return node;
				}
				// Otherwise, look for %
				else if (seek(parser,"%",left,right)) {
					SimpleNode<string> node("%");
					node.AddSubNode(ParseExpression(left));
					node.AddSubNode(ParseExpression(right));
					return node;
				}
				// Otherwise, it should be a terminal
				else if (leaf(parser,left))
					return SimpleNode<string>(left);
				// Otherwize error
				else throw Exceptions::ArithmeticsException("Syntax error : " + expr);
			}
		}

		/**
		 *	Evaluate an arithmetic expression tree returning the required type
		 */
		template <typename T> static T EvalExpression(
			const Types::SimpleNode<std::string> & node,
			std::map<std::string,T> & vars
		) {
			return static_cast<T>(evalSubExpression<T>(node,vars));
		}

		/**
		 *	Convert an arithmetic expression to a tree and evaluate it
		 */
		template <typename T> static T ParseAndEvalExpression(
			const std::string & expr,
			std::map<std::string,T> & vars
		) {
			Types::SimpleNode<std::string> tree = ParseExpression(expr);
			return EvalExpression<T>(tree,vars);
		}
	
	protected:

		static const bool seek(Tokeniser & parser, const std::string & op, std::string & left, std::string & right) {
			parser.Reset();
			left = ""; right = "";
			std::string token;
			int cpt = 0;
			bool op_found = false;
			do {
				token = parser.GetNextToken(false);
				if (token == "(") ++cpt;
				else if (token == ")") --cpt;
				if ((token == op) && (cpt == 0) && (!op_found))
					op_found = true;
				else {
					if (!op_found) left += token;
					else right += token;
				}
			}
			while (!parser.PreviewNextToken(false).empty());
			return op_found;
		}
		
		static const bool leaf(Tokeniser & parser, std::string & leaf) {
			parser.Reset();
			leaf = parser.GetNextToken(false);
			return parser.PreviewNextToken(false).empty();
		}
		
		static const bool isNumericValue(const std::string & str) {
			bool dot = false;
			for (unsigned int i=0; i<str.size(); ++i) {
				if ((str[i] == '.') || (str[i] == ',')) {
					if (dot) return false;
					else dot = true;
				}
				else if ((str[i] < '0') || (str[i] > '9'))
					return false;
			}
			return true;
		}
		
		/**
		 *	Evaluate an arithmetic expression tree returning a double
		 */	
		template <typename T> static double evalSubExpression(
			const Types::SimpleNode<std::string> & node,
			std::map<std::string,T> & vars
		) {
			// If leaf
			if (node.GetNbSubNodes() == 0) {
				if (vars.find(node.GetData()) != vars.end())
					return static_cast<double>(vars[node.GetData()]);
				else {
					if (!isNumericValue(node.GetData()))
						throw Exceptions::ArithmeticsException("Incorrect or unknown value : \"" + node.GetData() + "\"");
					std::stringstream ss; ss << node.GetData();
					double val; ss >> val;
					return val;
				}
			}
			// If binary node
			else if (node.GetNbSubNodes() == 2) {
				if (node.GetData() == "+")
					return evalSubExpression<T>(node.GetSubNode(0),vars) + evalSubExpression<T>(node.GetSubNode(1),vars);
				else if (node.GetData() == "-")
					return evalSubExpression<T>(node.GetSubNode(0),vars) - evalSubExpression<T>(node.GetSubNode(1),vars);
				else if (node.GetData() == "*")
					return evalSubExpression<T>(node.GetSubNode(0),vars) * evalSubExpression<T>(node.GetSubNode(1),vars);
				else if (node.GetData() == "/") {
					double divisor = evalSubExpression<T>(node.GetSubNode(1),vars);
					if (divisor == 0.) throw Exceptions::DivisionByZeroException("Division by zero");
					return evalSubExpression<T>(node.GetSubNode(0),vars) / divisor;
				}
				else if (node.GetData() == "^")
					return pow(evalSubExpression<T>(node.GetSubNode(0),vars),evalSubExpression<T>(node.GetSubNode(1),vars));
				else if (node.GetData() == "%")
					return static_cast<int>(evalSubExpression<T>(node.GetSubNode(0),vars)) % static_cast<int>(evalSubExpression<T>(node.GetSubNode(1),vars));
				else
					throw Exceptions::ArithmeticsException("Incorrect Arithmetic Operator : "+node.GetData());
			}
			else
				throw Exceptions::ArithmeticsException("Arithmetic expression nodes should be leaves or binary");
		}
		
};

////////////////////////////////////////////////////////////////////////////////
// Closing Namespaces
////////////////////////////////////////////////////////////////////////////////

}

////////////////////////////////////////////////////////////////////////////////

#endif

